/**
 * 301. 删除无效的括号
 * https://leetcode-cn.com/problems/remove-invalid-parentheses/
 */
const { displayBaseArray } = require('../../libs/public');

/**
 * @param {string} s
 * @return {boolean}
 */
function isInvalid(s) {
  let top = -1;
  for (let i = 0; i < s.length; i += 1) {
    if (s[i] === '(') {
      top += 1;
    } else if (s[i] === ')') {
      if (top < 0) {
        return false;
      }
      top -= 1;
    }
  }
  return top < 0;
}

/**
 * @param {string} s
 * @param {number} index
 * @param {number} leftToDelete
 * @param {number} leftRest
 * @param {number} rightToDelete
 * @param {number} rightRest
 * @param {Set<string>} result
 */
function dfs(s, index, leftToDelete, leftRest, rightToDelete, rightRest, result) {
  if (!leftToDelete && !rightToDelete) {
    if (isInvalid(s)) {
      result.add(s);
    }
    return;
  }
  if (s[index] === '(') {
    if (!leftToDelete) {
      dfs(s, index + 1, leftToDelete, leftRest - 1, rightToDelete, rightRest, result);
      return;
    }
    if (leftToDelete === leftRest) {
      dfs(`${s.substring(0, index)}${s.substring(index + 1)}`, index, leftToDelete - 1, leftRest - 1, rightToDelete, rightRest, result);
    } else {
      dfs(`${s.substring(0, index)}${s.substring(index + 1)}`, index, leftToDelete - 1, leftRest - 1, rightToDelete, rightRest, result);
      dfs(s, index + 1, leftToDelete, leftRest - 1, rightToDelete, rightRest, result);
    }
  } else if (s[index] === ')') {
    if (!rightToDelete) {
      dfs(s, index + 1, leftToDelete, leftRest, rightToDelete, rightRest - 1, result);
      return;
    }
    if (rightToDelete === rightRest) {
      dfs(`${s.substring(0, index)}${s.substring(index + 1)}`, index, leftToDelete, leftRest, rightToDelete - 1, rightRest - 1, result);
    } else {
      dfs(`${s.substring(0, index)}${s.substring(index + 1)}`, index, leftToDelete, leftRest, rightToDelete - 1, rightRest - 1, result);
      dfs(s, index + 1, leftToDelete, leftRest, rightToDelete, rightRest - 1, result);
    }
  } else {
    dfs(s, index + 1, leftToDelete, leftRest, rightToDelete, rightRest, result);
  }
}

/**
 * @param {string} s
 * @return {string[]}
 */
function removeInvalidParentheses(s) {
  let leftCount = 0;
  let leftToDelete = 0;
  let rightCount = 0;
  let rightToDelete = 0;
  let top = -1;
  let isStackAllLeft = false;
  for (let i = 0; i < s.length; i += 1) {
    if (s[i] === '(') {
      leftCount += 1;
      if (top < 0) {
        top = 0;
        isStackAllLeft = true;
      } else if (!isStackAllLeft) {
        rightToDelete += (top + 1);
        top = 0;
        isStackAllLeft = true;
      } else {
        top += 1;
      }
    } else if (s[i] === ')') {
      rightCount += 1;
      if (top < 0) {
        top = 0;
        isStackAllLeft = false;
      } else if (isStackAllLeft) {
        top -= 1;
      } else {
        top += 1;
      }
    }
  }
  if (top >= 0) {
    if (isStackAllLeft) {
      leftToDelete += (top + 1);
    } else {
      rightToDelete += (top + 1);
    }
  }
  const result = new Set();
  dfs(s, 0, leftToDelete, leftCount, rightToDelete, rightCount, result);
  return Array.from(result);
}

console.log(displayBaseArray(removeInvalidParentheses('()())()')) === '[(())(),()()()]');
console.log(displayBaseArray(removeInvalidParentheses('(a)())()')) === '[(a())(),(a)()()]');
console.log(removeInvalidParentheses(')(')[0] === '');
